RAID stands for Redundant Array of Independent Disks and is a taxonomy of redundant disk array storage schemes which define a number of ways of configuring and using multiple computer disk drives to achieve varying levels of availability, performance, capacity and cost while appearing to the software application as a single large capacity drive. Typical RAID storage subsystems can be implemented in either hardware or software. In the former instance, the RAID algorithms are packaged into separate controller hardware coupled to the computer input/output (“I/O”) bus and, although adding little or no central processing unit (“CPU”) overhead, the additional hardware required nevertheless adds to the overall system cost. On the other hand, software implementations incorporate the RAID algorithms into system software executed by the main processor together with the operating system, obviating the need and cost of a separate hardware controller, yet adding to CPU overhead.
Various RAID levels have been defined from RAID-0 to RAID-6, each offering tradeoffs in the previously mentioned factors. RAID-0 is nothing more than traditional striping in which user data is broken into chunks which are stored onto the stripe set by being spread across multiple disks with no data redundancy. RAID-I is equivalent to conventional “shadowing” or “mirroring” techniques and is the simplest method of achieving data redundancy by having, for each disk, another containing the same data and writing to both disks simultaneously. The combination of RAID-0 and RAID-1 is typically referred to as RAID-0+1 and is implemented by striping shadow sets resulting in the relative performance advantages of both RAID levels. RAID-2, which utilizes Hamming Code written across the members of the RAID set is not now considered to be of significant importance.
In RAID-3, data is striped across a set of disks with the addition of a separate dedicated drive to hold parity data. The parity data is calculated dynamically as user data is written to the other disks to allow reconstruction of the original user data if a drive fails without requiring replication of the data bit-for-bit. Error detection and correction codes (“ECC”) such as Exclusive-OR (“XOR”) or more sophisticated Reed-Solomon techniques may be used to perform the necessary mathematical calculations on the binary data to produce the parity information in RAID-3 and higher level implementations. While parity allows the reconstruction of the user data in the event of a drive failure, the speed of such reconstruction is a function of system workload and the particular algorithm used.
As with RAID-3, the RAID scheme known as RAID-4 consists of N data disks and one parity disk wherein the parity disk sectors contain the bitwise XOR of the corresponding sectors on each data disk. This allows the contents of the data in the RAID set to survive the failure of any one disk. RAID-5 is a modification of RAID-4 which stripes the parity across all of the disks in the array in order to statistically equalize the load on the disks.
The designation of RAID-6 has been used colloquially to describe RAID schemes that can withstand the failure of two disks without losing data through the use of two parity drives (commonly referred to as the “P” and “Q” drives) for redundancy and sophisticated ECC techniques. Although the term “parity” is used to describe the codes used in RAID-6 technologies, the codes are more correctly a type of ECC code rather than simply a parity code. Data and ECC information are striped across all members of the RAID set and write performance is generally lower than with RAID-5 because three separate drives must each be accessed twice during writes. However, the principles of RAID-6 may be used to recover a number of drive failures depending on the number of “parity” drives that are used.
Some RAID-6 implementations are based upon Reed-Solomon algorithms, which depend on Galois Field arithmetic. A complete explanation of Galois Field arithmetic and the mathematics behind RAID-6 can be found in a variety of sources and, therefore, only a brief overview is provided below as background. The Galois Field arithmetic used in these RAID-6 implementations takes place in GF(2N). This is the field of polynomials with coefficients in GF(2), modulo some generator polynomial of degree N. All the polynomials in this field are of degree N-1 or less, and their coefficients are all either 0 or 1, which means they can be represented by a vector of N coefficients all in {0,1}; that is, these polynomials “look” just like N-bit binary numbers. Polynomial addition in this Field is simply N-bit XOR, which has the property that every element of the Field is its own additive inverse, so addition and subtraction are the same operation. Polynomial multiplication in this Field, however, can be performed with table lookup techniques based upon logarithms or with simple combinational logic.
Each RAID-6 check code (i.e., P and Q) expresses an invariant relationship, or equation, between the data on the data disks of the RAID-6 array and the data on one or both of the check disks. If there are C check codes and a set of F disks fail, F≦C, the failed disks can be reconstructed by selecting F of these equations and solving them simultaneously in GF(2N) for the F missing variables. In the RAID-6 systems implemented or contemplated today there are only 2 check disks—check disk P, and check disk Q. It is worth noting that the check disks P and Q change for each stripe of data and parity across the array such that parity data is not written to a dedicated disk but is, instead, striped across all the disks.
Even though RAID-6 has been implemented with varying degrees of success in different ways in different systems, there remains an ongoing need to improve the efficiency and costs of providing RAID-6 protection for data storage. The mathematics of implementing RAID-6 involve complicated calculations that are also repetitive. Accordingly, efforts to improve the simplicity of circuitry, the cost of circuitry and the efficiency of the circuitry needed to implement RAID-6 remains a priority today and in the future.
For example, one limitation of existing RAID-6 designs relates to the performance overhead associated with performing resync (where parity data for a parity stripe is resynchronized with the current data), rebuild (where data from a faulty or missing drive is regenerated based upon the parity data) or other exposed mode operations such as exposed mode reads. A resync operation, for example, requires that, for each parity stripe defined in the disk array, the data must be read from all of the disks and used to solve a parity stripe equation by multiplying the data from each disk by an appropriate value and XOR'ing the multiplied data like a sum of products to construct a parity value for the parity stripe. In addition, the parity value calculated as the result of solving the parity stripe equation must be written to the appropriate disk. In addition, since RAID-6 designs rely on two parity values for each parity stripe, the aforementioned process typically must be performed twice for each parity stripe to generate and write both parity values to the disk array.
Likewise, to rebuild an exposed disk, data for each parity stripe must be read from all of the other disks and used to solve a parity stripe equation in a similar multiply-and-XOR manner as is used for resynchronization. The result of solving the parity stripe equation is the data that is written back to the exposed disk. In addition, for other exposed mode operations such as exposed mode read operations, a similar process to a rebuild operation must be performed, albeit without storing back the result of the parity stripe equation to the disk array.
In each of these exposed mode operations, however, the requirements of reading data from certain disks and writing data back to certain disks results in substantial performance overhead, specifically with respect to the sequential nature of the various disk access operations on the disk array. A substantial need therefore exists for a manner of improving the performance of a disk array system such as a RAID-6 system to improve performance in connection with resynchronization, rebuild and other exposed mode operations.